package com.peng.leetcode.array;

/**
 * MinPathSum
 * 剑指 Offer II 099. 最小路径之和
 * https://leetcode.cn/problems/0i0mDW/
 *
 * @author: lupeng6
 * @create: 2023/2/18 18:33
 */
public class MinPathSum {
    private int ans = Integer.MAX_VALUE;
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        dfs(grid, 0, 0, 0);
        return ans;
    }

    void dfs(int[][] grid, int i, int j, int sum) {
        if (i == (grid.length - 1) && j == (grid[0].length - 1)) {
            ans = Math.max(ans, sum);
            return;
        }
        if (i < grid.length) {
            dfs(grid, i + 1, j, sum + grid[i][j]);
        }
        if (j < grid[0].length) {
            dfs(grid, i ,j + 1, sum + grid[i][j]);
        }
    }
}
